1. Field of the Invention
The present inventions relates to bus arbitration and in particular to a bus arbitration method and structure for using lookup tables for determining and applying parameters of arbitration for control of a shared resource.
2. Related Patents
This patent is related to commonly owned U.S. patent application Ser. No. 10/162,960, filed 5 Jun. 2002, entitled METHODS AND STRUCTURE FOR IMPROVED FAIRNESS BUS ARBITRATION and is related to commonly owned U.S. patent application Ser. No. 10/164,240, filed 5 Jun. 2002, entitled METHODS AND STRUCTURE FOR STATE PRESERVATION TO IMPROVE FAIRNESS IN BUS ARBITRATION, both of which are hereby incorporated herein by reference.
3. Discussion of Related Art
It is generally known in electronic systems to have multiple devices communicating over a shared electronic bus. In general, a first device (usually referred to as a master device) initiates an exchange of information with a second device (usually referred to as a slave device). It is also generally known in the art that a bus structure may permit multiple master devices and multiple slave devices to exchange information. Generally, one master device communicates with one or more slave devices to the exclusion of other master and slave devices in the system. In such a circumstance, a first master device desiring use of the bus for communication with a slave device must first obtain temporary exclusive control over the shared bus structure. A master device obtains temporary exclusive control of the shared bus by requesting the bus structure and awaiting an acknowledgment signal indicative of granting of the requested temporary exclusive access to the shared bus.
Typically, an arbiter device coupled to the shared bus structure receives a request for temporary exclusive control of the bus from each of several master devices and selects the next master device to obtain the requested temporary exclusive control. The arbiter receives request signals and returns grant (acknowledgment) signals to master devices to indicate request and granting of temporary exclusive control, respectively. This process is typically referred to as the bus arbitration. A number of well-known commercially applied bus structures support such multiple master devices sharing control of a bus. Though the specific timing and signals involved in arbitration may vary, all such buses support arbitration in some form.
It is common in the art for an arbiter device to utilize any of several well-known techniques for determining the next requesting master device to be granted temporary exclusive control of the shared bus structure. One simple technique is often referred to as “round-robin” in that each device may be granted temporary exclusive control of the shared bus in sequential order defined by an index number—usually a master device ID. When the last master device ID is granted temporary exclusive control over the bus, the first master device is again eligible for exclusive bus control. This sequential “round-robin” technique assures that each master device has a roughly equal opportunity to obtain temporary exclusive control of the shared bus structure.
Another common bus arbitration technique is to assign a priority to each master device. At any given point, a master device with the highest priority requesting temporary exclusive control of the shared bus will be granted control over the bus. Still other techniques combine features of both a priority-based scheme and round-robin arbitration techniques. For example, each master device may be assigned a priority and all master devices having the same particular priority level share the bus using a round-robin technique.
Strict round-robins arbitration generally provides equal access to the shared bus for all master devices. Standard priority-based bus arbitration algorithms are effective at assuring that the highest priority master devices can rapidly access the shared bus as compared to lower priority devices. However a problem with priority-based scheme is that the lowest priority devices may be effectively “starved” from access to the bus due to high frequency bus requests by higher priority master devices. By contrast, round-robin arbitration techniques preclude high priority master devices from obtaining necessary frequent access to a shared bus.
Hybrid techniques, as noted above, that combine features of both round-robin arbitration and priority-based arbitration still produce unfair results in some circumstances. For example, presume a plurality of master devices are requesting the bus all at the same first priority level (i.e., applying round-robin techniques within that priority level). A higher priority master device then requests and is granted the bus (since it is a higher priority than the plurality of devices at the first priority level). When the higher priority device relinquishes the bus, the plurality of devices at the first priority level again arbitrate using round-robin techniques.
The particular arbitration structures and methods appropriate to a system are determined by a system designer with consideration of parameters and circumstances of the particular system. Present arbitration techniques are generally algorithmic in nature and thus implemented as circuits performing a fixed function determined by the designer of the arbiter. This presents a problem where it is desirable to modify parameters of the arbitration technique after the arbiter is designed. Such changes require modification to the arbiter circuit design to modify the desired functionality of the arbiter. Further, it may be desirable to modify parameters of the arbitration process in response to measurement of operation of the system. Such dynamic alterations are not possible in present arbiter designs where a fixed circuit determines all parameters of the arbitration process.
It is evident from the above discussion that a need exists for improved flexibility in designing arbitration processes and in particular a need exists to enable flexible, dynamic alterations to arbitration processes in a system.